// https://leetcode.cn/problems/reformat-the-string/
// Created by ade on 2022/8/11.
//
#include <iostream>
#include <string>
#include <algorithm>


using namespace std;

class Solution {
public:
    string reformat1(string s) {
        int len = s.size();
        int num = 0;// 数字的数量
        num = count_if(s.begin(), s.end(), ::isdigit);

        if (2 * num - len > 1) return "";
        sort(s.begin(), s.end());
        string newS = "";
        for (int i = 0; i < len / 2; i++) {
            newS += s[i];
            newS += s[num + i];
        }

        if (num * 2 > len) {
            newS += s[num - 1];
        } else if (num * 2 < len) {
            newS = s[len - 1] + newS;
        }

        return newS;
    }

    string reformat2(string s) {
        int len = s.size();
        if (len == 1) return s;
        int num = 0;// 数字的数量
        num = count_if(s.cbegin(), s.cend(), ::isdigit);
        int cNum = len - num;
        if (abs(num - cNum) > 1) return "";
        if (cNum > num) sort(s.rbegin(), s.rend());
        else sort(s.begin(), s.end());

        if (len == 3) {
            swap(s[1], s[2]);
            return s;
        }

        int maxN = max(cNum, num);
        for (int i = 1; i <= (len - maxN) / 2; i++) {
            swap(s[2 * i - 1], s[2 * i - 1 + maxN]);
        }
        if (maxN % 2 == 0) {
            char c = s[len - maxN];
            s.erase(len - maxN, 1);
            s += c;
        }

        return s;
    }

};

int main() {
    Solution so;
//    string s = "77a";
    string s = "619mama";

    cout << so.reformat(s) << endl;
    return 0;
}